package practice1_100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Offer38 {
    List<String> Allres=new LinkedList<>();
    public String[] permutation(String s) {
        char[] chars=s.toCharArray();
        LinkedList<Character> res=new LinkedList<>();
        trackBack( res,chars);
        ;
        return (String[]) Allres.toArray();
    }

    private void trackBack(LinkedList<Character> res,char[] chars) {
        //base case
        if(res.size()==chars.length) {
            StringBuffer stringBuffer=new StringBuffer();
            for (char a:chars ) {
                stringBuffer.append(a);
            }
            Allres.add(stringBuffer.toString());
            return;
        }

        //
        for (int i = 0; i < chars.length; i++) {
            if(res.contains(chars[i])) continue;

            res.add(chars[i]);
            trackBack(res, chars);
            res.removeLast();
        }

    }

    public static void main(String[] args) {
        new Offer38().permutation("dsahfi");
    }
}
